{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Report - Sudoku\n",
    "\n",
    "* 姓名\n",
    "* 学号\n",
    "\n",
    "\n",
    "## 任务简介\n",
    "\n",
    "* 数独（Sudoku）是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3 * 3）内的数字均含1-9，不重复。本实验最终目标是通过机器学习的方法解决数独问题。\n",
    "\n",
    "* 提供的数据有一百万组数独，数据集包含2列。quizzes栏目是未解的游戏，solutions栏目各自的已解游戏。每场比赛都由81个数字组成的字符串表示。\n",
    "\n",
    "## 解决途径\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import keras\n",
    "import keras.backend as K\n",
    "from keras.optimizers import Adam\n",
    "from keras.models import Sequential\n",
    "from keras.utils import Sequence\n",
    "from keras.layers import *\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>quizzes</th>\n",
       "      <th>solutions</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0043002090050090010700600430060020871900074000...</td>\n",
       "      <td>8643712593258497619712658434361925871986574322...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>0401000501070039605200080000000000170009068008...</td>\n",
       "      <td>3461792581875239645296483719658324174729168358...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>6001203840084590720000060050002640300700800069...</td>\n",
       "      <td>6951273841384596727248369158512647392739815469...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4972000001004000050000160986203000403009000000...</td>\n",
       "      <td>4972583161864397252537164986293815473759641828...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>0059103080094030600275001000300002010008200070...</td>\n",
       "      <td>4659123781894735623275681497386452919548216372...</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                                             quizzes  \\\n",
       "0  0043002090050090010700600430060020871900074000...   \n",
       "1  0401000501070039605200080000000000170009068008...   \n",
       "2  6001203840084590720000060050002640300700800069...   \n",
       "3  4972000001004000050000160986203000403009000000...   \n",
       "4  0059103080094030600275001000300002010008200070...   \n",
       "\n",
       "                                           solutions  \n",
       "0  8643712593258497619712658434361925871986574322...  \n",
       "1  3461792581875239645296483719658324174729168358...  \n",
       "2  6951273841384596727248369158512647392739815469...  \n",
       "3  4972583161864397252537164986293815473759641828...  \n",
       "4  4659123781894735623275681497386452919548216372...  "
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "path = \"D:/myjupyter/report_03_Sudoku/\"\n",
    "data = pd.read_csv(path+\"sudoku.csv\")\n",
    "try:\n",
    "    data = pd.DataFrame({\"quizzes\":data[\"puzzle\"],\"solutions\":data[\"solution\"]})\n",
    "except:\n",
    "    pass\n",
    "data.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class 'pandas.core.frame.DataFrame'>\n",
      "RangeIndex: 1000000 entries, 0 to 999999\n",
      "Data columns (total 2 columns):\n",
      " #   Column     Non-Null Count    Dtype \n",
      "---  ------     --------------    ----- \n",
      " 0   quizzes    1000000 non-null  object\n",
      " 1   solutions  1000000 non-null  object\n",
      "dtypes: object(2)\n",
      "memory usage: 15.3+ MB\n"
     ]
    }
   ],
   "source": [
    "data.info()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Quiz:\n",
      " [[0 0 4 3 0 0 2 0 9]\n",
      " [0 0 5 0 0 9 0 0 1]\n",
      " [0 7 0 0 6 0 0 4 3]\n",
      " [0 0 6 0 0 2 0 8 7]\n",
      " [1 9 0 0 0 7 4 0 0]\n",
      " [0 5 0 0 8 3 0 0 0]\n",
      " [6 0 0 0 0 0 1 0 5]\n",
      " [0 0 3 5 0 8 6 9 0]\n",
      " [0 4 2 9 1 0 3 0 0]]\n",
      "Solution:\n",
      " [[8 6 4 3 7 1 2 5 9]\n",
      " [3 2 5 8 4 9 7 6 1]\n",
      " [9 7 1 2 6 5 8 4 3]\n",
      " [4 3 6 1 9 2 5 8 7]\n",
      " [1 9 8 6 5 7 4 3 2]\n",
      " [2 5 7 4 8 3 9 1 6]\n",
      " [6 8 9 7 3 4 1 2 5]\n",
      " [7 1 3 5 2 8 6 9 4]\n",
      " [5 4 2 9 1 6 3 7 8]]\n"
     ]
    }
   ],
   "source": [
    "print(\"Quiz:\\n\",np.array(list(map(int,list(data['quizzes'][0])))).reshape(9,9))\n",
    "print(\"Solution:\\n\",np.array(list(map(int,list(data['solutions'][0])))).reshape(9,9))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 深度学习方法\n",
    "\n",
    "我们知道语义对于解决数独问题很重要，而卷积神经网络在保留语义和提取语义特征方面是理想的，因此我们将创建一个卷积神经网络。\n",
    "* 我们的输入是一系列的shape(9,9)数组。\n",
    "* 输出的shape为 (81,1)，因此我们使用sparse_categorical_crossentropy 损失函数，不需要传递 one-hot 向量作为输出。\n",
    "* 我们使用 640 的批量大小，因为数据数量非常大，并且可以很容易地放入合适的 GPU 中。\n",
    "* 训练和验证拆分为 95% 到 5%，因为 9M 的 5% 也非常大（4,50,000）。\n",
    "* 使用减少 lr 方法来微调我们的模型和模型检查点，以保存最佳模型并避免过度拟合。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DataGenerator(Sequence):\n",
    "    def __init__(self, df,batch_size = 16,subset = \"train\",shuffle = False, info={}):\n",
    "        super().__init__()\n",
    "        self.df = df\n",
    "        self.batch_size = batch_size\n",
    "        self.shuffle = shuffle\n",
    "        self.subset = subset\n",
    "        self.info = info\n",
    "        \n",
    "        self.data_path = path\n",
    "        self.on_epoch_end()\n",
    "        \n",
    "    def __len__(self):\n",
    "        return int(np.floor(len(self.df)/self.batch_size))\n",
    "    def on_epoch_end(self):\n",
    "        self.indexes = np.arange(len(self.df))\n",
    "        if self.shuffle==True:\n",
    "            np.random.shuffle(self.indexes)\n",
    "            \n",
    "    def __getitem__(self,index):\n",
    "        X = np.empty((self.batch_size, 9,9,1))\n",
    "        y = np.empty((self.batch_size,81,1))\n",
    "        indexes = self.indexes[index*self.batch_size:(index+1)*self.batch_size]\n",
    "        for i,f in enumerate(self.df['quizzes'].iloc[indexes]):\n",
    "            self.info[index*self.batch_size+i]=f\n",
    "            X[i,] = (np.array(list(map(int,list(f)))).reshape((9,9,1))/9)-0.5\n",
    "        if self.subset == 'train': \n",
    "            for i,f in enumerate(self.df['solutions'].iloc[indexes]):\n",
    "                self.info[index*self.batch_size+i]=f\n",
    "                y[i,] = np.array(list(map(int,list(f)))).reshape((81,1)) - 1\n",
    "        if self.subset == 'train': return X, y\n",
    "        else: return X"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "model = Sequential()\n",
    "\n",
    "model.add(Conv2D(64, kernel_size=(3,3), activation='relu', padding='same', input_shape=(9,9,1)))\n",
    "model.add(BatchNormalization())\n",
    "model.add(Conv2D(64, kernel_size=(3,3), activation='relu', padding='same'))\n",
    "model.add(BatchNormalization())\n",
    "model.add(Conv2D(128, kernel_size=(1,1), activation='relu', padding='same'))\n",
    "\n",
    "model.add(Flatten())\n",
    "model.add(Dense(81*9))\n",
    "model.add(Reshape((-1, 9)))\n",
    "model.add(Activation('softmax'))\n",
    "\n",
    "adam = keras.optimizers.Adam(lr=.001)\n",
    "model.compile(loss='sparse_categorical_crossentropy', optimizer=adam, metrics=['accuracy'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Model: \"sequential_2\"\n",
      "_________________________________________________________________\n",
      "Layer (type)                 Output Shape              Param #   \n",
      "=================================================================\n",
      "conv2d_6 (Conv2D)            (None, 9, 9, 64)          640       \n",
      "_________________________________________________________________\n",
      "batch_normalization_4 (Batch (None, 9, 9, 64)          256       \n",
      "_________________________________________________________________\n",
      "conv2d_7 (Conv2D)            (None, 9, 9, 64)          36928     \n",
      "_________________________________________________________________\n",
      "batch_normalization_5 (Batch (None, 9, 9, 64)          256       \n",
      "_________________________________________________________________\n",
      "conv2d_8 (Conv2D)            (None, 9, 9, 128)         8320      \n",
      "_________________________________________________________________\n",
      "flatten_2 (Flatten)          (None, 10368)             0         \n",
      "_________________________________________________________________\n",
      "dense_2 (Dense)              (None, 729)               7559001   \n",
      "_________________________________________________________________\n",
      "reshape_2 (Reshape)          (None, 81, 9)             0         \n",
      "_________________________________________________________________\n",
      "activation_2 (Activation)    (None, 81, 9)             0         \n",
      "=================================================================\n",
      "Total params: 7,605,401\n",
      "Trainable params: 7,605,145\n",
      "Non-trainable params: 256\n",
      "_________________________________________________________________\n"
     ]
    }
   ],
   "source": [
    "model.summary()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 数据生成器\n",
    "创建训练和测试数据生成器。 使用 95% 的数据进行训练，使用 5% 的数据进行验证，因为 9Million 中的 5% 对于验证来说仍然非常大。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "train_idx = int(len(data)*0.95)\n",
    "data = data.sample(frac=1).reset_index(drop=True)\n",
    "training_generator = DataGenerator(data.iloc[:train_idx], subset = \"train\", batch_size=640)\n",
    "validation_generator = DataGenerator(data.iloc[train_idx:], subset = \"train\",  batch_size=640)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(640, 9, 9, 1)"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "training_generator.__getitem__(4)[0].shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 回调函数\n",
    "\n",
    "回调有助于随时随地监控模型训练。 它们可用于停止训练、保存最佳权重、在验证准确性没有提高的情况下降低学习率。\n",
    "\n",
    "在本实验中，我使用了两个回调。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "from keras.callbacks import Callback, ModelCheckpoint, ReduceLROnPlateau\n",
    "filepath1=\"weights-improvement-{epoch:02d}-{val_accuracy:.2f}.hdf5\"\n",
    "filepath2 = \"best_weights.hdf5\"\n",
    "checkpoint1 = ModelCheckpoint(filepath1, monitor='val_accuracy', verbose=1, save_best_only=True, mode='max')\n",
    "checkpoint2 = ModelCheckpoint(filepath2, monitor='val_accuracy', verbose=1, save_best_only=True, mode='max')\n",
    "\n",
    "reduce_lr = ReduceLROnPlateau(\n",
    "    monitor='val_loss',\n",
    "    patience=3,\n",
    "    verbose=1,\n",
    "    min_lr=1e-6\n",
    ")\n",
    "callbacks_list = [checkpoint1,checkpoint2,reduce_lr]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1484/1484 [==============================] - ETA: 0s - loss: 0.3718 - accuracy: 0.1109\n",
      "Epoch 00001: val_accuracy did not improve from 0.11107\n",
      "\n",
      "Epoch 00001: val_accuracy did not improve from 0.11107\n",
      "1484/1484 [==============================] - 507s 341ms/step - loss: 0.3718 - accuracy: 0.1109 - val_loss: 0.3702 - val_accuracy: 0.1074\n"
     ]
    }
   ],
   "source": [
    "history = model.fit_generator(training_generator, validation_data = validation_generator, epochs = 1, verbose=1,callbacks=callbacks_list )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "model.load_weights('best_weights.hdf5')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在这里，我尝试使用一种更人性化的方法来解决数独，即一次填充一个数字。 这意味着将数独通过神经网络一次并填充它最确定的数字，然后再次通过它并填充另一个数字直到所有数字都被填充。 这有助于神经网络从先前填充的数字中获取上下文信息，就像人类玩家一样。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "def norm(a):\n",
    "    return (a/9)-.5\n",
    "\n",
    "def denorm(a):\n",
    "    return (a+.5)*9\n",
    "\n",
    "def inference_sudoku(sample):\n",
    "    \n",
    "    '''\n",
    "        This function solve the sudoku by filling blank positions one by one.\n",
    "    '''\n",
    "    \n",
    "    feat = sample\n",
    "    \n",
    "    while(1):\n",
    "    \n",
    "        out = model.predict(feat.reshape((1,9,9,1)))  \n",
    "        out = out.squeeze()\n",
    "\n",
    "        pred = np.argmax(out, axis=1).reshape((9,9))+1 \n",
    "        prob = np.around(np.max(out, axis=1).reshape((9,9)), 2) \n",
    "        \n",
    "        feat = denorm(feat).reshape((9,9))\n",
    "        mask = (feat==0)\n",
    "     \n",
    "        if(mask.sum()==0):\n",
    "            break\n",
    "            \n",
    "        prob_new = prob*mask\n",
    "    \n",
    "        ind = np.argmax(prob_new)\n",
    "        x, y = (ind//9), (ind%9)\n",
    "\n",
    "        val = pred[x][y]\n",
    "        feat[x][y] = val\n",
    "        feat = norm(feat)\n",
    "    \n",
    "    return pred\n",
    "\n",
    "def test_accuracy(feats, labels):\n",
    "    \n",
    "    correct = 0\n",
    "    \n",
    "    for i,feat in enumerate(feats):\n",
    "        \n",
    "        pred = inference_sudoku(feat)\n",
    "        \n",
    "        true = labels[i].reshape((9,9))+1\n",
    "        \n",
    "        if(abs(true - pred).sum()==0):\n",
    "            correct += 1\n",
    "        \n",
    "    print(correct/feats.shape[0])\n",
    "\n",
    "def solve_sudoku(game):\n",
    "    \n",
    "    game = game.replace('\\n', '')\n",
    "    game = game.replace(' ', '')\n",
    "    game = np.array([int(j) for j in game]).reshape((9,9,1))\n",
    "    game = norm(game)\n",
    "    game = inference_sudoku(game)\n",
    "    return game"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "您可以在“game”字符串中放入任何游戏来解决它。只需复制游戏字符串中的new_game字符串，并修改所需的零。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "solved puzzle:\n",
      "\n",
      "[[1 8 4 7 5 3 2 9 6]\n",
      " [5 2 3 4 6 9 1 7 8]\n",
      " [6 9 7 2 8 1 5 4 3]\n",
      " [8 7 5 1 3 2 9 6 4]\n",
      " [9 6 1 5 7 8 3 1 2]\n",
      " [4 3 2 6 9 1 7 8 5]\n",
      " [7 5 9 8 4 4 6 3 1]\n",
      " [3 1 8 9 2 6 4 5 7]\n",
      " [2 4 6 3 1 5 8 2 9]]\n"
     ]
    }
   ],
   "source": [
    "new_game = '''\n",
    "          0 0 0 0 0 0 0 0 0\n",
    "          0 0 0 0 0 0 0 0 0\n",
    "          0 0 0 0 0 0 0 0 0\n",
    "          0 0 0 0 0 0 0 0 0\n",
    "          0 0 0 0 0 0 0 0 0\n",
    "          0 0 0 0 0 0 0 0 0\n",
    "          0 0 0 0 0 0 0 0 0\n",
    "          0 0 0 0 0 0 0 0 0\n",
    "          0 0 0 0 0 0 0 0 0\n",
    "      '''\n",
    "\n",
    "game = '''\n",
    "          0 0 0 7 0 0 0 9 6\n",
    "          0 0 3 0 6 9 1 7 8\n",
    "          0 0 7 2 0 0 5 0 0\n",
    "          0 7 5 0 0 0 0 0 0\n",
    "          9 0 1 0 0 0 3 0 0\n",
    "          0 0 0 0 0 0 0 0 0\n",
    "          0 0 9 0 0 0 0 0 1\n",
    "          3 1 8 0 2 0 4 0 7\n",
    "          2 4 0 0 0 5 0 0 0\n",
    "      '''\n",
    "\n",
    "game = solve_sudoku(game)\n",
    "\n",
    "print('solved puzzle:\\n')\n",
    "print(game)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([45, 45, 45, 45, 42, 45, 47, 45, 40], dtype=int64)"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.sum(game, axis=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们可以看到，这个模型在训练集上的准确率并不高，并不是解决数独的理想方法。神经网络的建立是为了一般化，但对于这个问题并不理想。有更好的方法来实现这一点，使用正常的编程，如下面给出的一个使用回溯来解决问题。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve(bo):\n",
    "    find = find_empty(bo)\n",
    "    if not find:\n",
    "        return True\n",
    "    else:\n",
    "        row, col = find\n",
    "\n",
    "    for i in range(1,10):\n",
    "        if valid(bo, i, (row, col)):\n",
    "            bo[row][col] = i\n",
    "\n",
    "            if solve(bo):\n",
    "                return True\n",
    "\n",
    "            bo[row][col] = 0\n",
    "\n",
    "    return False\n",
    "\n",
    "\n",
    "def valid(bo, num, pos):\n",
    "    # Check row\n",
    "    for i in range(len(bo[0])):\n",
    "        if bo[pos[0]][i] == num and pos[1] != i:\n",
    "            return False\n",
    "\n",
    "    # Check column\n",
    "    for i in range(len(bo)):\n",
    "        if bo[i][pos[1]] == num and pos[0] != i:\n",
    "            return False\n",
    "\n",
    "    # Check box\n",
    "    box_x = pos[1] // 3\n",
    "    box_y = pos[0] // 3\n",
    "\n",
    "    for i in range(box_y*3, box_y*3 + 3):\n",
    "        for j in range(box_x * 3, box_x*3 + 3):\n",
    "            if bo[i][j] == num and (i,j) != pos:\n",
    "                return False\n",
    "\n",
    "    return True\n",
    "\n",
    "\n",
    "def print_board(bo):\n",
    "    for i in range(len(bo)):\n",
    "        if i % 3 == 0 and i != 0:\n",
    "            print(\"- - - - - - - - - - - - - \")\n",
    "\n",
    "        for j in range(len(bo[0])):\n",
    "            if j % 3 == 0 and j != 0:\n",
    "                print(\" | \", end=\"\")\n",
    "\n",
    "            if j == 8:\n",
    "                print(bo[i][j])\n",
    "            else:\n",
    "                print(str(bo[i][j]) + \" \", end=\"\")\n",
    "\n",
    "\n",
    "def find_empty(bo):\n",
    "    for i in range(len(bo)):\n",
    "        for j in range(len(bo[0])):\n",
    "            if bo[i][j] == 0:\n",
    "                return (i, j)  # row, col\n",
    "\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 8 4  | 7 5 3  | 2 9 6\n",
      "5 2 3  | 4 6 9  | 1 7 8\n",
      "6 9 7  | 2 1 8  | 5 4 3\n",
      "- - - - - - - - - - - - - \n",
      "8 7 5  | 6 3 2  | 9 1 4\n",
      "9 6 1  | 5 4 7  | 3 8 2\n",
      "4 3 2  | 8 9 1  | 7 6 5\n",
      "- - - - - - - - - - - - - \n",
      "7 5 9  | 3 8 4  | 6 2 1\n",
      "3 1 8  | 9 2 6  | 4 5 7\n",
      "2 4 6  | 1 7 5  | 8 3 9\n"
     ]
    }
   ],
   "source": [
    "game = '''\n",
    "          0 0 0 7 0 0 0 9 6\n",
    "          0 0 3 0 6 9 1 7 8\n",
    "          0 0 7 2 0 0 5 0 0\n",
    "          0 7 5 0 0 0 0 0 0\n",
    "          9 0 1 0 0 0 3 0 0\n",
    "          0 0 0 0 0 0 0 0 0\n",
    "          0 0 9 0 0 0 0 0 1\n",
    "          3 1 8 0 2 0 4 0 7\n",
    "          2 4 0 0 0 5 0 0 0\n",
    "      '''\n",
    "game = game.strip().split(\"\\n\")\n",
    "board = []\n",
    "for i in game:\n",
    "    t = i.replace(' ','').strip()\n",
    "    t = list(t)\n",
    "    t = list(map(int,t))\n",
    "    board.append(t)\n",
    "    \n",
    "if solve(board):\n",
    "    print_board(board)\n",
    "else:\n",
    "    print(\"Can't be solved.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([45, 45, 45, 45, 45, 45, 45, 45, 45])"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.sum(board, axis=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "来看看这个算法有多快。我将解决第一个1000个问题，看看准确性和速度。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "1000it [00:00, 31270.44it/s]\n"
     ]
    }
   ],
   "source": [
    "val_set = data.iloc[:1000]\n",
    "\n",
    "\n",
    "from tqdm import tqdm\n",
    "quiz_list = list(val_set['quizzes'])\n",
    "sol_list = list(val_set['solutions'])\n",
    "val_quiz = []\n",
    "val_sol = []\n",
    "for i,j in tqdm(zip(quiz_list,sol_list)):\n",
    "    q = np.array(list(map(int,list(i)))).reshape(9,9)\n",
    "    s = np.array(list(map(int,list(j)))).reshape(9,9)\n",
    "    val_quiz.append(q)\n",
    "    val_sol.append(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "1000it [00:09, 100.58it/s]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1000/1000 solved!! That's 100.0% accuracy.\n",
      "\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "count = 0\n",
    "for i,j in tqdm(zip(val_quiz,val_sol)):\n",
    "    if solve(i):\n",
    "        if (i==j).all():\n",
    "            count+=1\n",
    "    else:\n",
    "        pass\n",
    "    \n",
    "print(\"{}/1000 solved!! That's {}% accuracy.\\n\".format(count,(count/1000.0)*100))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们可以看到，虽然它达到了100%的准确率，但速度很慢，因为它花费了很多时间解决1000个问题。继续尝试一些更好的方法。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "\n",
    "import collections\n",
    "\n",
    "rows = 'ABCDEFGHI'\n",
    "cols = '123456789'\n",
    "\n",
    "def cross(A, B):\n",
    "    return [s + t for s in A for t in B]\n",
    "\n",
    "\n",
    "boxes = cross(rows, cols)\n",
    "\n",
    "row_units = [cross(r, cols) for r in rows]\n",
    "column_units = [cross(rows, c) for c in cols]\n",
    "square_units = [cross(rs, cs) for rs in ('ABC', 'DEF', 'GHI') for cs in ('123', '456', '789')]\n",
    "unitlist = row_units + column_units + square_units \n",
    "units = dict((s, [u for u in unitlist if s in u]) for s in boxes)\n",
    "peers = dict((s, set(sum(units[s], [])) - set([s])) for s in boxes)\n",
    "\n",
    "\n",
    "def assign_value(values, box, value):\n",
    "    values[box] = value\n",
    "    return values\n",
    "\n",
    "\n",
    "def naked_twins(values):   \n",
    "    for unit in unitlist:\n",
    "        unit_values_counter = collections.Counter([values[box] for box in unit])\n",
    "        for twins, count in unit_values_counter.items():\n",
    "            if 1 < count == len(twins):\n",
    "                for box in unit:\n",
    "                    if values[box] != twins and set(values[box]).intersection(set(twins)):\n",
    "                        for digit in twins:\n",
    "                            values = assign_value(values, box, values[box].replace(digit, ''))\n",
    "    return values\n",
    "\n",
    "\n",
    "def grid_values(grid):\n",
    "    chars = []\n",
    "    digits = '123456789'\n",
    "    for c in grid:\n",
    "        if c in digits:\n",
    "            chars.append(c)\n",
    "        if c == '0':\n",
    "            chars.append(digits)\n",
    "    assert len(chars) == 81\n",
    "    return dict(zip(boxes, chars))\n",
    "\n",
    "\n",
    "def display(values):\n",
    "    width = 1 + max(len(values[s]) for s in boxes)\n",
    "    line = '+'.join(['-' * (width * 3)] * 3)\n",
    "    for r in rows:\n",
    "        print(''.join(values[r + c].center(width) + ('|' if c in '36' else '')\n",
    "                      for c in cols))\n",
    "        if r in 'CF': print(line)\n",
    "    print\n",
    "\n",
    "\n",
    "def eliminate(values):\n",
    "    solved_values = [box for box in values.keys() if len(values[box]) == 1]\n",
    "    for box in solved_values:\n",
    "        digit = values[box]\n",
    "        for peer in peers[box]:\n",
    "            values[peer] = values[peer].replace(digit, '')\n",
    "    return values\n",
    "\n",
    "\n",
    "def only_choice(values):\n",
    "    for unit in unitlist:\n",
    "        for digit in '123456789':\n",
    "            dplaces = [box for box in unit if digit in values[box]]\n",
    "            if len(dplaces) == 1:\n",
    "                values[dplaces[0]] = digit\n",
    "    return values\n",
    "\n",
    "\n",
    "def reduce_puzzle(values):\n",
    "    stalled = False\n",
    "    while not stalled:\n",
    "        solved_values_before = len([box for box in values.keys() if len(values[box]) == 1])\n",
    "        values = eliminate(values)\n",
    "        values = only_choice(values)\n",
    "        values = naked_twins(values)\n",
    "        solved_values_after = len([box for box in values.keys() if len(values[box]) == 1])\n",
    "        stalled = solved_values_before == solved_values_after\n",
    "        if len([box for box in values.keys() if len(values[box]) == 0]):\n",
    "            return False\n",
    "    return values\n",
    "\n",
    "\n",
    "def search(values):\n",
    "    values = reduce_puzzle(values)\n",
    "    if values is False:\n",
    "        return False  \n",
    "    if all(len(values[s]) == 1 for s in boxes):\n",
    "        return values  \n",
    "    min_possibility_box = min([box for box in boxes if len(values[box]) > 1])\n",
    "    for digit in values[min_possibility_box]:\n",
    "        new_sudoku = values.copy()\n",
    "        new_sudoku[min_possibility_box] = digit\n",
    "        attempt = search(new_sudoku)\n",
    "        if attempt:\n",
    "            return attempt\n",
    "\n",
    "\n",
    "def solve2(grid):\n",
    "\n",
    "    values = grid_values(grid)\n",
    "    values = search(values)\n",
    "    return values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "1000it [00:02, 412.40it/s]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1000/1,000 solved!! That's 100.0% accuracy.\n",
      "\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "count = 0\n",
    "for row in tqdm(data.head(1000).iterrows()):\n",
    "    if (solve2(row[1][\"quizzes\"]) == grid_values(row[1][\"solutions\"])):\n",
    "        count+=1\n",
    "        \n",
    "print(\"{}/1,000 solved!! That's {}% accuracy.\\n\".format(count,(count/1000.0)*100))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这个方法确实比回溯快。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 总结\n",
    "* 从以上解决数独的实验中，我发现神经网络在这个任务中不是很准确，也不是理想的候选。他们在更一般的任务中表现得更好，而不是非常具体和算术的任务。\n",
    "* 使用回溯可以解决一个数独，但它是非常缓慢的，因为它使用了多个组合作为它的进展。\n",
    "* 经过网上查询资料，根据这个实验，目前最好的方法是Naked Twins方法。这种方法有更好的版本，甚至比这种方法更快，叫做Naked Triplets 甚至Naked Quadruples。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  },
  "main_language": "python"
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
